Матч 431, Мегахолодные числа (MegaCoolNumbers)

Дивизион 1, Уровень 2

Положительное число называется холодным степени а, если его можно разбить на а групп рядом стоящих цифр, где цифры в каждой группе образуют арифметическую прогрессию. Положительное число называется мегахолодным степени а, если оно холодное степени а, но не является холодным степени а – 1, а все его цифры находятся в неубывающем порядке.

Вычислить количество мегахолодных чисел степени а, которые содержат в точности n цифр (без ведущих нулей). Ответ вернуть по модулю 1,000,000,007.

Класс: MegaCoolNumbers

Метод: int count(int n, int a)

Ограничения: 1 £ a, n £ 1000.

Вход. Два натуральных числа а и n.

Выход. Количество мегахолодных чисел степени а, которые содержат в точности n цифр. Ответ вернуть по модулю 1,000,000,007.

Пример входа

n	a
1	1
2	1
10	3

Пример выхода

9

45

7502

РЕШЕНИЕ

динамическое программирование

Если число из n цифр можно разбить на x < n прогрессий, то его можно разбить и на x + 1 прогрессию. Это можно совершить, взяв любую прогрессию содержащую как минимум две цифры и разбив ее на две части. Мегахолодное число будет иметь степень а, но не а – 1, только если а является наименьшей возможной степенью холодности этого числа.

Например, число 12345 является 3 – холодным (его можно разбить на части 123, 4, 5), но не 3 – мегахолодным, так как оно в свою очередь является 2-холодным (123, 45). Число 12345 является 1 – мегахолодным (но не 2 – мегахолодным, так как является 1 – холодным: все цифры числа 12345 образуют неубывающую арифметическую прогрессию).

Заметим, что мегахолодное число не может иметь степень больше 9. Так как все цифры мегахолодного числа расположены в неубывающем порядке, то одинаковые цифры должны стоять рядом. Для каждой цифры i мы можем образовать прогрессию, содержащую только цифры i. Количество прогрессий будет не более 9, поэтому наименьшая степень холодности такого числа не может быть больше 9.

Наименьшую степень холодности числа можно определить с помощью следующего жадного алгоритма. Присвоим первую цифру числа первой прогрессии. Для каждой следующей цифры проверяем, может ли она продлить текущую прогрессию. Если нет – создаем новую прогрессию, содержащую изначально только эту цифру.

Разобъем все i - цифровые мегахолодные числа на классы (pow, diff, last), где

pow – наименьшая степень холодности числа;

diff – разница последней прогрессии в числе (прогрессии образуются жадным алгоритмом, описанным выше). Специальное значение diff = 9 обозначает, что последняя прогрессия состоит из одного числа и ее разница не определена.

last – последняя цифра числа.

Подсчитаем количество чисел каждого класса последовательно для i = 1, 2, 3, …, n. Для i = 1 имеется ровно одно число для каждого класса вида (1, 9, d), 1 £ d £ 9 и 0 чисел для остальных классов.

Рассмотрим, как имея информацию о классах для чисел длины i, получить данные о классах для чисел длины i + 1. Перебираем имеющиеся классы чисел длины i и для каждого из них смотрим, какие числа можно получить добавлением одной цифры. Воспользуемся следующими правилами:

· К каждому числу из класса (pow, 9, last) можно добавить любую цифру d, last £ d £ 9, продлив последнюю прогрессию этой цифрой. В результате получим число из класса (pow, d – last, d).

· К каждому числу из класса (pow, diff, last), 0 £ diff < 9, можно добавить любую цифру d, last £ d £ 9. Если d – last = diff, то мы можем продлить последнюю прогрессию и получить число из класса (pow, diff, d). Иначе необходимо начинать новую прогрессию и новое число будет принадлежать классу (pow + 1, 9, d).

Ответом задачи будет количество всех чисел в классах (a, diff, last), принадлежащих n - цифровым мегахолодным числам.

ПРОГРАММА

#include <stdio.h>

#include <memory.h>

#define MOD 1000000007

int f[1000][10][10][10];

class MegaCoolNumbers

{

public:

int count(int n, int a)

{

int i, pow, last, diff, d, res;

if (a > 9) return 0;

memset(f,0,sizeof(f));

for(d = 1; d <= 9; d++)

f[1][1][9][d] = 1;

for (i = 1; i < n; i++)

for (pow = 1; pow <= 9; pow++)

for (last = 1; last <= 9; last++)

{

for (d = last; d <= 9; d++)

{

f[i+1][pow][d-last][d] += f[i][pow][9][last];

f[i+1][pow][d-last][d] %= MOD;

}

for (diff = 0; diff <= 8; diff++)

for (d = last; d <= 9; d++)

if (d - last == diff)

{

f[i+1][pow][diff][d] += f[i][pow][diff][last];

f[i+1][pow][diff][d] %= MOD;

} else if (pow < 9)

{

f[i+1][pow+1][9][d] += f[i][pow][diff][last];

f[i+1][pow+1][9][d] %= MOD;

}

}

res = 0;

for (last = 1; last <= 9; last++)

for (diff = 0; diff <= 9; diff++)

res = (res + f[n][a][diff][last]) % MOD;

return res;

}

};